從重複辨識找到第一個正式定律

繼續 昨天 的定律推敲，首先來想一下如何辨識 0 到 n 次的字元 'a'，

def many[A](p: Parser[A]): Parser[List[A]]

那如果想用 Parser[Int] 知道字元 'a' 出現幾次呢？我們可以考慮用 map function 實現，

def map[A, B](a: Parser[A])(f: A => B): Parser[B]

如此就能以以下組合調用來知道字元 'a' 出現幾次（先假裝 many 跟 map 已經放在 extension 底下）；

val numA: Parser[Int] = char('a').many.map(_.size)

numA.run("aaa") == Right(3)
numA.run("b") == Right(0)

到此，我們對 map 有個強烈的預期是它只轉換那些成功解析的 Parser，解析失敗的 Parser 不會透過 map 變成成功的，反之亦然，map 會成為各種 library 中一種必定保留的結構，因此有一個正式定律出來了。

map(p)(a => a) == p

因為有了 map，昨天 提到的 char function 就能用 map 實現了，

def char(c: Char): Parser[Char] =
  string(c.toString).map(_.charAt(0))       

跟其它組合用 function 類似，我們也能用 map 來實現 succeed function，空字串的 Parser 在面對任何輸入字串時都會成功。

def succeed[A](a: A): Parser[A] =
  string("").map(_ => a)

從 Parser 中取得解析成功的部份輸入：slice

many 和 map 的組合的確可以得出重複匹配次數，但有些沒有效率，因為我們從 List[Char] 中捨棄了值，只用到 size，這裡應該能透過一個 function 取得部份的 input 的話，就能省略了中間層資料結構 List 的產生，

def slice[A](p: Parser[A]): Parser[String]

然後就能這樣使用，

slice(char('a').many).run("aaba") == Right("aa")

這樣我在用 slice(char('a').many).map(_.size) 的時候，操作的會是 "aa" 這個字串，基於這點，slice 很值得放在核心 APi 之中。

非空的重複辨識

就是辨識 1 到 n 次的意思啦，我們用 many1 來表示，

def many1[A](p: Parser[A]): Parser[List[A]]

感覺起來 many1 應該是 many 的子項目，而實際上，many1(p) 就是解析器 p 先執行後，然後在針對同一個輸入字串執行 many(p)，這樣就能做到辨識 "1" 到 n 次，所以我們應該需要一個 function，讓我們能執行完一個 p解析器後，在執行另一個 p2 解析器，

def product[A, B](p: Parser[A], p2: Parser[B]): Parser[(A, B)]

我們也可以新增 ** 符號 function 來代表 product。

Exercise D20-1

用 product 實作 map2 function，它能用 high-order function 把 2 個 Parser 中的值轉換。

def map2[A, B, C](p: Parser[A], p2: Parser[B])(f: (A, B) => C): Parser[C]

有了 many1 和 product，我們就用以下調用解析 0 到多個 'a' 或 1 到多個 'b'。

val zeroOrMoreAFollowedByOneOrMoreB = char('a').many.slice.map(_.size) ** char('b').many1.slice.map(_.size)

zeroOrMoreAFollowedByOneOrMoreB.run("bbb") == Right(0, 3)
zeroOrMoreAFollowedByOneOrMoreB.run("aaab") == Right(1, 4)
zeroOrMoreAFollowedByOneOrMoreB.run("aaabbbab") == Right(3, 3)

接下來讓我們來嘗試實現 many，

def many[A](p: Parser[A]): Parser[List[A]] =
  map2(p, many(p))(_ :: _) | succeed(Nil)

使用 map2 是因為我們想要先執行 p 解析器，然後在遞迴的執行 many(p)（因為 many 是要辨識 0 到 n 次），然後將值透過 :: 合併，如果一開始就辨識失敗，起碼還有 0 次的空 List 可回傳，

但這裡有個問題是，Scala function 預設是 strict，所以 map2 的調用會是無窮迴圈，

所以我們要把 map2 的第 2 個參數改為 non-strict，這樣 p2 不會立即執行，除非 p 解析成功，

def map2[A, B, C](p: Parser[A], p2: => Parser[B])(f: (A, B) => C): Parser[C]

相對應的 product 的第 2 個參數也要改為 non-strict，

def product[A, B](p: Parser[A], p2: => Parser[B]): Parser[(A, B)]

最後順便也把 昨天 的 or 改為 non-strict 吧！

extension[A] (p: Parser[A])

	def or(p2: => Parser[A]): Parser[A]
	infix def |(p2: => Parser[A]): Parser[A] = p.or(p2)

明天繼續！

Day 20 - Exercise answer